import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-06-17
 * Time:9:09
 */
public class TestHeap {
    public int[] elem;
    public int useSides;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void shiftDown(int parent, int len) {
        int child = parent * 2 + 1;
        while (child < len) {
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void createHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            useSides++;
        }
        for (int parent = (useSides - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, this.useSides);
        }
    }

    public void isFull(){
        if(elem.length==useSides){
            this.elem=Arrays.copyOf(this.elem,useSides*2);
        }
    }

    public void shiftUp(int child){
        int parent=(child - 1)/2;
        while(parent>=0){
            if (child + 1 < useSides && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[parent] < elem[child]) {
                swap(parent,child);
                child=parent;
                parent=(child - 1)/2;
            }else{
                break;
            }
        }
    }
    /*
    入堆
     */
    public void offer(int val){
        isFull();
        this.elem[this.useSides]=val;
        this.useSides++;
        shiftUp(this.useSides-1);
    }

    /*
    出堆
    删除堆顶元素，因为堆顶元素的优先级最高
    1、第一个元素与最后一个元素交换
    2、this.useSize--（引用类型要进行置空）
    3、只需要调整0下标这棵树
     */
    public int poll(){
        if(isEmpty()){
            System.out.println("出堆时队列为空");
            throw new RuntimeException();
        }
        int ret=this.elem[0];
        swap(0,this.useSides-1);
        this.useSides--;
        shiftDown(0,this.useSides);
        return ret;
    }

    /*
    判断空
     */
    public boolean isEmpty(){
        return this.useSides == 0;
    }

    public void swap(int a,int b){
        int tmp = elem[a];
        elem[a] = elem[b];
        elem[b] = tmp;
    }

    public void heapSort(){
        int end=this.useSides-1;
        while(end>=0){
            //交换元素
            swap(0,end);
            //调整为大根堆
            shiftDown(0,end);
            end--;
        }
    }
}
